---
title: "求值"
created: 2025-11-28
tags:
  - 算法
---

# 求值

## 题目 [求值](https://www.lanqiao.cn/paper/3845/problem/816/)

![[image-d8ba6d62.png]]

## 思路分析

问题是有100个约数的最小的数是多少 因为是填空题 所有最暴力的想法就是 直接从小到大枚举 看每个数有多少个约数 第一次找到约数数量有100个的数时
就是答案

约数数量怎么求呢

可以用试除法 把一个数的所有约数找出来放在set里 最后返回set的size 就是该数的约数数量

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=100010;

int counts(int n){

	set<int> res;

	for(int i=1;i<=n/i;i++){

		if(n%i==0){

			res.insert(i);

			res.insert(n/i);

		}

	}

	return res.size();

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	for(int i=0;i<1000000;i++){

		if(counts(i)==100){

			cout<<i;

			return 0;

		}

	}

	return 0;

}
```

相当暴力 但也是得到了正确答案

填空题 这题其实可以这样过了

但是 复习一下约数

约数个数有个公式

把一个数N 写成：N = (p1^x1)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数。

则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)

但是貌似并不适用 因为这个公式适用于知道因子的情况 而这里并不知道因子 还得把因子求出来 再套公式 那既然求出了因子 直接放set里其实更快

如果对于一个给定数 **n** 需要计算它的约数个数，存在两种基本方法：

**1. 试除法（暴力方法）**

您提到的使用试除法是直接且直观的方法，这种方法的优点是编码简单，适合于范围较小或约数数量较少的数。具体实现方式如您所示，通过遍历从 1 到
$\sqrt{n}$ 的所有整数来检查每个数是否为 **n** 的约数，如果是，则它和 **n** 除以它的结果都是约数。

**2. 分解质因数法**

此方法基于数的质因数分解，如您所述，一个数 **N** 可以表示为 $N=p_1^{x_1}\cdot p_2^{x_2}\cdots p_k^{x_k}$，其中
$p_i$ 是质数，$x_i$ 是对应的指数。然后，**N** 的约数个数是
$$(x_1+1)\cdot(x_2+1)\cdots(x_k+1)$$

使用这种方法需要先找出 **n** 的所有质因数及其指数。这可以通过试除法进行，即从最小的质数开始，尝试能否整除 **n**，并计算每个质数的指数。然后应用上述公式计算约数总数。这种方法的复杂度取决于 **n** 的质因数分解速度，对于大数而言，如果其因数结构复杂（如有很多小的质因数），则这种方法会比直接计算约数要快。

**对于问题的应用**

如果问题是找到最小的数，它恰好有 100 个约数，暴力方法虽然直接但效率较低，特别是当数变得很大时。质因数分解方法在找到最小的满足条件的数时可能更高效，因为它允许我们快速计算一个数的约数个数，而不必实际地找出所有约数。

**示例代码优化**

考虑到约数个数的计算，如果使用质因数分解方法，代码可以修改为：

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

int divisorCount(int n) {

    int cnt = 1;

    for (int i = 2; i <= n / i; ++i) {

        if (n % i == 0) {

            int power = 0;

            while (n % i == 0) {

                n /= i;

                ++power;

            }

            cnt *= (power + 1);

        }

    }

    if (n > 1) cnt *= 2;

    return cnt;

}

int main() {

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    for (int i = 1; ; ++i) {

        if (divisorCount(i) == 100) {

            cout << i << endl;

            break;

        }

    }

    return 0;

}
```

这种优化考虑了除法和质因数分解，更适合处理较大的数字和复杂的约数问题。

代码2真的会比代码1效率高吗 在我看来也是找到了一个属的所有约数吧 它甚至对每个约数做了额外的操作 如果更优 体现在哪里

对于比较两段代码的效率，我们首先要了解它们的计算原理和复杂度。两者都是计算一个数字的约数数量，但方法和内部操作有所不同。

**试除法与质因数分解法的比较：**

**试除法 (第一段代码)**

- **操作**：对于每个整数 **i**，检查 **n % i == 0**。如果为真，则 **i** 和 **n/i** 都是 **n** 的约数。
- **复杂度**：对于每个数，最坏情况下的操作次数是 $O(n)$，因为它检查从
  1 到 $n$ 的所有整数。
- **数据结构**：使用 **set** 存储约数，保证唯一性，但插入操作平均具有 $O(\log k)$
  的时间复杂度，其中 **k** 是集合中元素的数量。

**质因数分解法 (第二段代码)**

- **操作**：对于每个整数 **i**，同时计算 **n** 由 **i** 整除的次数（即 **i** 的幂），直到 **n** 不再被 **i** 整除。
- **复杂度**：对每个质因子 **i** 执行整除操作，最坏情况下是 $O(n)$。但由于它跳过了所有已经被较小的质因子整除的数，这通常比简单的试除法要快。
- **数据结构**：没有使用额外的数据结构来存储约数，而是直接通过乘法计算总约数数目，省去了存储和查找的时间。

**效率对比**

- **数据存储**：第一段代码使用 **set**，这意味着每找到一个新约数都需要进行插入操作。尽管 **set** 操作是对数时间复杂度，但是在频繁插入时仍然会造成时间消耗。而第二段代码直接通过计算获得结果，没有额外的数据存储和管理开销。
- **计算次数**：第二段代码在确定 **i** 是 **n** 的质因数后，会立即计算 **i** 的幂，这避免了对每个 **i** 的多次重复检查。而第一段代码对每个 **i** 只做一次检查，但需要额外处理 **n/i**。
- **内部循环**：第二段代码减少了循环中的重复计算。当 **i** 不再是 **n** 的因数时，它跳出内层循环，而第一段代码则对每个 **i** 至少计算两次（**i** 和 **n/i**）。

**总结**

虽然两者在理论上都是 $O(n)$ 的时间复杂度，质因数分解法在实际应用中往往效率更高，特别是对于大数。它避免了不必要的存储和管理开销，并且减少了重复计算。因此，在处理需要频繁计算大量数的约数数量的情况下，质因数分解法通常是更优的选择。

## 代码实现

```

```

## 同类题型

## 视频讲解

---
⬅️ [[拼接|拼接]] 🏠 [[00-冲刺国赛]] ➡️ [[路径计数|路径计数]]